%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Copyright Malte Helmert, Universitaet Freiburg
%%% All Rights Reserved
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Dieser Text verwendet eine BibTeX-Literaturdatenbank und ist daher etwas
%%% komplizierter zu uebersetzen als LaTeX-Texte, bei denen dies nicht der
%%% Fall ist:
%%%   # latex tbedl.tex
%%%   # bibtex tbedl
%%%   # latex tbedl.tex
%%%   # latex tbedl.tex
%%%   # dvips tbedl.dvi
%%% Die mehrfachen LaTeX-Laeufe sind tatsaechlich notwendig. Nach dem ersten
%%% Lauf "weiss" BibTeX, welche Artikel in dem Text zitiert werden und kann
%%% diese zusammensuchen. Beim zweiten LaTeX-Lauf werden die Zitate dann
%%% ordnungsgemaess von LaTeX verarbeitet, wodurch sich aber unter Umstaenden
%%% gegenueber dem ersten Lauf hier und da noch Seitengrenzen verschieben
%%% koennen, was wiederum Seitenverweise a la "Abbildung 5 auf Seite 23"
%%% ungueltig machen kann. Deswegen wird der dritte LaTeX-Lauf notwendig.
%%% Abschliessend erzeugt dann dvips die Postscript-Datei.
%%%
%%% Natuerlich kann man auch pdflatex verwenden, um PDF-Output zu erzeugen.
%%% Dann lauten die noetigen Aufrufe:
%%%   # pdflatex tbedl.tex
%%%   # bibtex tbedl
%%%   # pdflatex tbedl.tex
%%%   # pdflatex tbedl.tex

\documentclass[a4paper,12pt]{article}

\usepackage{german}
%%% Heutzutage besser "ngerman" verwenden (neue deutsche Rechtschreibung und
%%% Silbentrennung). Um Umlaute und scharfes S direkt eingeben zu koennen, kann
%%% man
%%%   \usepackage[latin1]{inputenc}
%%% bemuehen, handelt sich dann aber evtl. Probleme ein, wenn man den Text auf
%%% einem System editieren moechte, das Umlaute anders kodiert.

\usepackage{bibgerm}
%%% Dieses Paket ist fuer die Verwendung der deutschen Zitierstile
%%% erforderlich. Steht es nicht zur Verfuegung (es gehoert nicht zum
%%% LaTeX-Standard, allerdings zu allen in Deutschland verbreiteten
%%% LaTeX-Distributionen), muss diese Zeile entfernt und der Zitierstil
%%% geaendert werden (siehe \bibliographystyle am Ende dieser Datei). Fuer
%%% englischsprachige Dokumente ist das Paket nicht erforderlich.

\usepackage{epic}
%% Dient dem Erstellen von Lininendiagrammen (s. Abbildung 1, S. 11). Es ist
%% allerdings in der Regel schmerzfreier, derartige Abbildungen nicht von Hand
%% zu erzeugen, sondern Zeichenprogramme wie xfig oder Funktionsplotter wie
%% gnuplot zu verwenden.

\newcommand{\zitat}[1]{\glqq #1\grqq}
%%% "\zitat" erzeugt ,,deutsche'' Anfuehrungszeichen.

\pagestyle{headings}
%%% Erzeugt die Abschnittsueberschriften und Seitenzahlen in der Kopfzeile.

\begin{document}

\title{Titel}
\author{Givenname Familyname}
\date{01.~May 2009}
\maketitle
%%% Erzeugt einen Titel mit den drei angegebenen Elementen.

\vspace{\fill}
%%% Fuegt an dieser Stelle so viel Abstand ein, dass diese Seite nach unten
%%% buendig abschliesst (d.h. die folgende Box erscheint ganz unten.)

\begin{small}
\begin{center}
\begin{tabular}{|l|} \hline
Reading Assignment \\
Informatik Theorie I \\
University of Freiburg \\
SS 2009 \\ \hline
\end{tabular}
\end{center}
\end{small}
%%% Tabellen sind der einfachste Weg, Text einzurahmen und den gesamten Rahmen
%%% zu zentrieren. Wir verwenden hier eine kleinere Schrift.


\thispagestyle{empty}
%%% Keine Seitenzahl auf der Titelseite

\clearpage
%%% Titelseite fertig, Seitenumbruch erzwingen.

\section{"Ubersicht}
Diese Seminararbeit befa"st sich mit \emph{transformation-based error-driven
learning}, einer allgemeinen Methode im Bereich der korpus-basierten
Sprachverarbeitung, und ihrer Anwendung im Bereich des \emph{part of speech
tagging}. Die Arbeit beruht im Wesentlichen auf einem Artikel von Eric Brill
\cite{brill}.

In den folgendenen beiden Abschnitten werden zun"achst das Problem des part of
speech tagging sowie die allgemeine Technik des transformation-based
error-driven learning vorgestellt.

Darauf folgen zwei Algorithmen zur L"osung dieses Problems mithilfe der
vorgestellten Technik, zun"achst eine nicht lexikalisierte Variante, bei der
die benutzten Transformationen sich ausschlie"slich auf die Tags des
Textk"orpers beziehen, danach eine lexikalisierte Variante, bei der auch
Transformationen zugelassen sind, die auf spezielle W"orter des Lexikons Bezug
nehmen. Anschlie"send wird auf das Problem unbekannter W"orter eingegangen.

Im abschlie"senden Teil werden die vorgestellten Algorithmen evaluiert und zu
anderen aktuellen Methoden zur L"osung der vorgestellten Probleme in Beziehung
gesetzt. Die Schlu"sbetrachtungen nehmen eine Bewertung der vorgestellten
Technik vor.

\section{Part of Speech Tagging}
Beim \emph{part of speech tagging} geht es darum, den W"ortern eines
Textk"orpers algorithmisch die zugeh"origen Wortarten zuzuordnen. Je nach
Anwendungsgebiet kann die Einteilung in Kategorien verh"altnism"a"sig grob
sein (\emph{Verb}, \emph{Substantiv}, \emph{Adjektiv}, \dots), oder aber
deutlich feinere Unterscheidungen treffen (\emph{Substantiv-Singular},
\emph{Verb-Infinitiv}, \dots). Part of speech tagger bilden eine fr"uhe Phase
in nat"urlichsprachlichen Systemen und k"onnen dort beispielsweise die
Grundlage einer syntaktischen Analyse bilden \cite{russell}.

Es ist nicht m"oglich, das part of speech tagging-Problem durch einfache
W"orterb"ucher zu l"osen, da die eigentliche Schwierigkeit in einer Vielzahl
von Mehrdeutigkeiten liegt, die nur durch den Kontext aufgel"ost werden
k"onnen. Betrachten wir dazu das folgende Beispiel\footnote{Da f"ur die
  vorgestellten Algorithmen nur empirische Daten f"ur englischsprachige Texte
  vorliegen, werden hier und im folgenden englischsprachige Beispiele
  verwendet. Die Anwendbarkeit des Ansatzes auf andere nat"urliche Sprachen
  wird im abschlie"senden Abschnitt angesprochen.}:

\begin{enumerate}
\item It was a calm night.
\item He tried to calm the mob.
\item On the third day, the ship came into a calm.
\end{enumerate}

Im ersten Satz wird \emph{calm} als Adjektiv gebraucht, im zweiten Satz als
Verb, im dritten schlie"slich als Substantiv. Interessanterweise ist es in den
meisten F"allen m"oglich, diese Unterscheidung automatisch zu inferieren, ohne
den Sinn der Aussagen zu erfassen, indem grammatikalisches Wissen "uber die
englische Sprache benutzt wird. So steht beim ersten Satz das Wort \emph{calm}
zwischen dem Artikel \emph{a} und dem Substantiv \emph{night}, was die
Verwendung als Adjektiv nahelegt. Im zweiten Fall geht das Wort \emph{to}
voraus und es folgt das Artikel-Substantiv-Paar \emph{the mob}, was auf ein
Verb schlie"sen l"a"st. Im dritten Beispielsatz schlie"slich steht \emph{calm}
zwischen dem Artikel \emph{a} und dem Satzendezeichen und ist daher vermutlich
ein Substantiv.

Derartige "Uberlegungen f"uhrten zur Verwendung stochastischer, auf
Markovmodellen basierender $n$-gramm-Tagger. Hierbei werden anhand annotierter
(also bereits mit Tags versehener) Beispieltexte kontextuelle bedingte
Wahrscheinlichkeiten gelernt, die Aussagen dar"uber machen, wie wahrscheinlich
das Auftreten eines bestimmten Tags ist, wenn ihm $n$ bestimmte Tags
vorhergehen.

Der Tagging-Algorithmus ordnet dann einem Satz $w_1 \dots w_m$ eine Tag-Folge
$t_1 \dots t_n$ zu, die f"ur jedes Wort $w_i$ das Produkt
$P(w_i | t_i) \cdot P(t_i | t_{i-1} \dots t_{i-n})$ maximiert.

Im folgenden soll eine andere Methode vorgestellt werden, die ebenfalls auf
der Verwendung annotierter Textk"orper beruht, allerdings im Gegensatz zu den
stochastischen Modellen eine relativ explizite Darstellung des gelernten
linguistischen Wissens benutzt und wesentlich weniger speicherintensiv ist.

\section{Transformation-Based Error-Driven Learning}
Beim Ansatz des \emph{transformation-based error-driven learning} wird anhand
eines annotierten Trainingstextes eine Liste von \emph{Transformationen}
gelernt, die einen nicht (oder falsch) annotierten Text in einen weitgehend
korrekt annotierten Text "uberf"uhren sollen. Dies geschieht wie folgt:

\begin{enumerate}
\item Versehe den Trainingstext durch den \emph{Startannotator} (\emph{initial
state annotator}) mit einer vorl"aufigen Annotierung. Dies k"onnte z.B. eine
zuf"allige Annotierung sein, oder aber eine erste N"aherung, etwa unter
Verwendung eines Lexikons, das jedem Wort sein h"aufigstes Tag zuordnet, ohne
den Kontext zu ber"ucksichtigen.
\item W"ahle aus der Menge der m"oglichen Transformationen ein \zitat{bestes
Element} aus. F"uge dieses an die Liste der gelernten Transformationen an und
wende es auf den Text an.
\item Wiederhole Schritt 2., bis ein Abbruchkriterium erf"ullt ist.
\end{enumerate}

Durch diesen Algorithmus wird also eine (geordnete) Liste von
Transformationsregeln gelernt. Wenn sp"ater ein neuer Text annotiert werden
soll, geschieht dies einfach dadurch, da"s zun"achst der Startannotator darauf
angewandt wird und anschlie"send die gelernten Regeln der Reihe nach benutzt
werden, um diese anf"angliche Annotation zu transformieren. Das Verfahren
"ahnelt also den stochastischen $n$-gramm-Taggern in der Hinsicht, da"s
zun"achst anhand eines Beispieltextes linguistisches Wissen gesammelt wird,
das dann zur Annotation anderer Texte verwendet wird.

Der obige Algorithmus beinhaltet im Wesentlichen vier Freiheitsgrade:
\begin{itemize}
\item Die Wahl des Startannotators: N"aheres hierzu bei der Besprechung der
verschiedenen Varianten in den n"achsten Abschnitten.
\item Die Menge der zul"assigen Transformationen: Dies ist das wesentliche
unterscheidende Kriterium der verschiedenen Varianten, daher folgt N"aheres
dazu in den entsprechenden Abschnitten.
\item Die Methode zur Auswahl der besten Transformation: Hier verfolgt Brill
einen einfachen \emph{Greedy}-Ansatz, w"ahlt also jeweils eine Transformation,
die die Zahl der falsch annotierten W"orter am st"arksten reduziert.
\item Die Abbruchbedingung: Bei Brill wird abgebrochen, sobald keine
Transformation mehr gefunden werden kann, die eine wesentliche Reduktion der
Fehlerzahl bewirkt. 
\end{itemize}

\subsection{Transformationen}
Eine Transformation besteht aus zwei Teilen, einer \emph{Modifikationsregel}
(\emph {rewrite rule}) und einer ausl"osenden Umgebung (\emph{triggering
environment}). Ein Beispiel f"ur eine Modifikationsregel ist etwa:
\zitat{"Andere das Tag von Verb zu Substantiv}, eine ausl"osende Umgebung
daf"ur \zitat{Das vorhergehende Wort ist ein Artikel}. Diese Transformation
w"urde die folgende falsche Annotation korrigieren: \\
$\phantom{Bla}$ John/Eigenname caught/Verb a/Artikel fly/Verb ./Satzende \\
Nach Anwendung der Transformation erg"abe sich dann: \\
$\phantom{Bla}$ John/Eigenname caught/Verb a/Artikel fly/Substantiv
./Satzende

Die Anwendung einer Transformation auf den Text geschieht derart, da"s der
Text Wort f"ur Wort durchgegangen wird, und an jeder Stelle, die eine
ausl"osende Umgebung markiert, die Modifikationsregel angewandt wird.

Die Durchlaufreihenfolge ist dabei von links nach rechts --- diese Angabe ist
wichtig, da die Anwendung der Modifikationsregel die Umgebung der
nachfolgenden W"orter beeinflussen kann. So f"uhrt etwa die Regel
\zitat{"Andere das Tag von $A$ nach $B$, falls ein Wort mit Tag $A$ vorangeht}
angewandt auf die Tag-Folge \emph{A A A A A A} bei einer Abarbeitung von links
nach rechts zu der Tag-Folge: \emph{A B A B A B}, bei einer Abarbeitung von
rechts nach links hingegen zu der Tag-Folge \emph{A B B B B B}.

\subsection{Transformationslisten vs. Entscheidungsb"aume}
Um ein Gef"uhl f"ur die M"achtigkeit von Listen von Transformationen zu geben,
soll hier ein kurzer Vergleich zwischen Transformationslisten und den
wohlbekannten Entscheidungsb"aumen (\emph{decision trees}) vorgenommen werden.
Brill hat gezeigt \cite{brill}, da"s die Menge der Klassifikationsprobleme,
die durch Entscheidungsb"aume gel"ost werden k"onnen, eine echte Teilmenge
derjenigen Probleme ist, die durch Transformationslisten gel"ost werden
k"onnen, wenn beiden dieselbe Menge an primitiven Anfragen (\emph{queries})
zur Verf"ugung steht.

An dieser Stelle soll eine H"alfte des Beweises gef"uhrt werden: Jede
Klassifikation mithilfe von Entscheidungsb"aumen kann auch mit
Transformationslisten durchgef"uhrt werden. Der einfacheren Darstellung wegen
beschr"anken wir uns auf bin"are Entscheidungsb"aume. Knoten h"oheren Grades
k"onnen analog behandelt werden. Der Beweis wird durch Induktion "uber dem
Aufbau des Entscheidungsbaumes gef"uhrt. $\top$ bezeichnet dabei die triviale
Anfrage, die immer wahr ist.

\paragraph*{Basisfall:}
Ein primitiver Entscheidungsbaum liefert die Klassifikation $A$, falls die
Antwort auf die Anfrage $X?$ wahr ist, die Klassifikation $B$ sonst.

Dies entspricht der folgenden Transformationsliste:
\begin{enumerate}
\item Anfangstag: Beschrifte mit $S$.
\item Wenn $X$, dann $S \rightarrow A$.
\item Wenn $\top$, dann $S \rightarrow B$.
\end{enumerate}

\paragraph*{Induktionsschritt:}
Sei jetzt $T$ ein Baum, der an der Wurzel die Anfrage $X?$ beinhaltet und nach
$T_1$ bzw. $T_2$ verzweigt, je nach dem, ob die Antwort ja oder nein lautet.

Nach Induktionsvoraussetzung existieren zu $T_1$ und $T_2$ entsprechende
Transformationslisten $L_1$ und $L_2$. Die erste Transformation von $L_1$
setze das Anfangstag $S_1$, die erste Transformation von $L_2$ setze das
Anfangstag $S_2$. Ohne Einschr"ankung trete $S_1$ in $L_2$ nicht auf, ebenso
$S_2$ nicht in $L_1$.

Die Transformationsliste zu $T$ beginnt dann wie folgt:
\begin{enumerate}
\item Anfangstag: Beschrifte mit $S$.
\item Wenn $X$, dann $S \rightarrow S_1$.
\item Wenn $\top$, dann $S \rightarrow S_2$.
\end{enumerate}
Es folgen die Regeln aus $L_1$ und schlie"slich die Regeln aus $L_2$.
Offensichtlich f"uhrt die Anwendung dieser Transformationsliste  zu derselben
Klassifikation wie die Auswertung des Entscheidungsbaums.

\section{Die Algorithmen}
Da beide im folgenden vorgestellten Algorithmen das Lexikon und den
Startannotator gemeinsam haben, sollen diese zun"achst erkl"art werden.

In einem Preprocessing-Schritt werden zun"achst alle im Trainingstext
auftretenden W"orter mit allen zugeh"origen Tags in ein Lexikon eingetragen.
F"ur jedes Wort wird dabei das am h"aufigsten auftretende Tag markiert. Das
Lexikon bildet also W"orter auf Mengen von Tags ab, die immer jeweils ein
ausgezeichnetes Element enthalten, das wir als \emph{Standard-Tag} bezeichnen
wollen.

Der Startannotator geht nun einfach den zu annotierenden Text durch und
versieht jedes Wort mit seinem Standard-Tag. Wir gehen zun"achst davon aus,
da"s der zu annotierende Text keine unbekannten W"orter enth"alt; diese
Annahme wird sp"ater im Abschnitt \emph{Unbekannte W"orter} aufgegeben.

\subsection{Der nicht lexikalisierte Algorithmus}
Der nicht lexikalisierte Algorithmus verwendet ausschlie"slich auf Tags
basierende Transformationen. Dies bedeutet jedoch nicht, da"s er keinerlei
lexikalische Information verwendet: allen Transformationen ist gemeinsam, da"s
ihre Modifikationsregel \zitat{"Andere Tag $A$ nach Tag $B$} bei einem Wort
$w$ nur dann feuert, wenn entweder $w$ nicht im Lexikon auftritt oder $B$ laut
Lexikon eines der m"oglichen Tags f"ur $w$ ist. Eine Transformation wird also
niemals einem Wort, "uber das lexikalische Informationen vorliegen, ein Tag
zuordnen, das nicht im zugeh"origen Lexikoneintrag vermerkt ist.

Die Transformationen des nicht-lexikalisierten Algorithmus entsprechen den
folgenden Schemata:

"Andere beim aktuellen Wort das Tag $A$ nach $B$, falls
\begin{enumerate}
\item Das vorhergehende (folgende) Wort das Tag $Z$ besitzt.
\item Das zweite Wort davor (dahinter) das Tag $Z$ besitzt.
\item Eines der beiden vorhergehenden (folgenden) W"orter das Tag $Z$ besitzt.
\item Eines der drei vorhergehenden (folgenden) W"orter das Tag $Z$ besitzt.
\item Das vorhergehende Wort das Tag $Z$ und das folgende Wort das Tag $W$
besitzt.
\item Das vorhergehende (folgende) Wort das Tag $Z$ und das zweite Wort davor
(dahinter) das Tag $W$ besitzt.
\end{enumerate}

Die Menge der erlaubten Transformationen umfa"st nun alle Instantiierungen der
obigen Schemata mit Tags $A$, $B$, $W$ und $Z$. Geht man von ca.~30
verschiedenen Tags aus, ergeben sich so mehrere Millionen potentielle
Transformationen --- eine Zahl, die zwar sehr gro"s erscheint, aber durch
entsprechende Programmierung in den Griff zu bekommen ist. In \cite{brill}
wird dazu erw"ahnt, da"s durch Verwendung eines datengetriebenen
(\emph{data-driven}) Ansatzes nur solche Transformationen betrachtet werden,
die auch tats"achlich f"ur eine Verbesserung in Frage kommen.

\subsection{Der lexikalisierte Algorithmus}
Der lexikalisierte Algorithmus unterscheidet sich von der eben vorgestellten
Variante nur dadurch, da"s die Menge der m"oglichen Transformationen noch
durch weitere Schemata erweitert wird, in denen auch auf spezifische W"orter
Bezug genommen werden kann. Diese Schemata sind im Einzelnen:

"Andere beim aktuellen Wort das Tag $A$ nach $B$, falls
\begin{enumerate}
\item Das vorhergehende (folgende) Wort $w$ ist.
\item Das zweite Wort davor (dahinter) $w$ ist.
\item Eines der beiden vorhergehenden (folgenden) W"orter $w$ ist.
\item Das aktuelle Wort $w$ und das vorhergehende (folgende) Wort $x$ ist.
\item Das aktuelle Wort $w$ ist und das vorhergehende (folgende) Wort das Tag
$Z$ besitzt.
\item Das aktuelle Wort $w$ ist.
\item Das vorhergende (folgende) Wort $w$ ist und das vorhergehende (folgende)
Wort das Tag $Z$ besitzt.
\item Das aktuelle Wort $w$ ist, das vorhergehende (folgende) Wort $x$ ist
und das vorhergehene (folgende) Wort das Tag $Z$ besitzt.
\end{enumerate}

Wiederum stehen $A$, $B$ und $Z$ f"ur beliebige Tags, $w$ und $x$  f"ur
beliebige W"orter.

\subsection{Unbekannte W"orter}
Bisher wurde das Problem unbekannter W"orter im Startannotator nicht
behandelt. Dies soll jetzt nachgeholt werden. Um unbekannte W"orter mit Tags
zu versehen, wird ebenfalls eine Variante des transformation-based
error-driven learning benutzt, um Regeln zur Markierung unbekannter W"orter
durch Training mit einem bereits annotierten Text zu lernen.

Der Startannotator markiert dabei alle W"orter des Textes entweder mit
\emph{Substantiv} oder \emph{Substantiv-Eigenname}, je nach dem, ob diese
klein- oder gro"sgeschrieben sind. Danach werden dann wie oben erkl"art
Transformationen gelernt, die den folgenden Schemata entsprechen:

"Andere beim aktuellen Wort das Tag $A$ nach $B$, falls
\begin{enumerate}
\item Das Entfernen des Pr"afix (Suffix) $x$ ein Wort ergibt.
\item Die Zeichenkette $x$ ein Pr"afix (Suffix) des Wortes ist.
\item Das Hinzuf"ugen des Pr"afixes (Suffixes) $x$ ein Wort ergibt.
\item Das Wort $w$ jemals direkt davor (dahinter) auftritt.
\item Das Zeichen $z$ in dem Wort auftritt.
\end{enumerate}

Dabei steht $w$ f"ur ein beliebiges Wort, $x$ f"ur eine beliebige Zeichenkette
mit $1 \leq |x| \leq 4$ und $z$ f"ur ein beliebiges Zeichen.

\section{Empirische Ergebnisse}
In diesem Abschnitt sollen die Ergebnisse von Brills Experimenten mit den
vorgestellten Algorithmen dargestellt werden. Insbesondere sollen dabei der
Einflu"s der Gr"o"se des Trainingstextes, der Einflu"s der Lexikalisierung und
die Effizienz der Behandlung unbekannter W"orter betrachtet werden. Bei
s"amtlichen Experimenten bildete der \emph{Penn Treebank Wall Street Journal
Corpus} \cite{marcus} die Grundlage des Lernverfahrens und der Evaluation.

Zum Vergleich mit stochastischen $n$-gramm-Taggern wurde \cite{weischedel}
herangezogen. Leider liegen f"ur diesen Algorithmus nur Daten unter der
Annahme eines vollst"andigen Lexikons (\emph{closed vocabulary assumption})
vor, d.h. es wurde davon ausgegangen, da"s keine unbekannten W"orter auftreten
und alle m"oglichen Tags aller auftretenden W"orter bekannt sind. Um
vergleichbare Daten zu erhalten, wurde daher zus"atzlich auch eine Reihe von
Experimenten durchgef"uhrt, bei denen auch die W"orter des
\emph{Evaluationstextes} mit zugeh"origen Tags in das Lexikon eingetragen
wurden, bevor der Algorithmus gestartet wurde. Zum Lernen von Regeln wurde der
Evaluationstext selbstverst"andlich \emph{nicht} herangezogen. Diese Eintr"age
sind in Tabelle \ref{maintable} mit (CVA) markiert.

\begin{table}[hbtp]
\begin{center}
\begin{tabular}{|c|c|c|c|}\hline
Methode & \# W"orter   & \# Regeln/  & Treffer- \\
        & im Trai-     & Wahrschein- & rate     \\
        & ningstext    & lichkeiten  &          \\ \hline
stochastisch (CVA) & 64.000 & 6.170 & 96,3\% \\ \hline
stochastisch (CVA) & 1.000.000 & 10.000 & 96,7\% \\ \hline
Transformationen, lex. (CVA) & 64.000 & 215 & 96,7\% \\ \hline
Transformationen, lex. (CVA) & 600.000 & 447 & 97,2\% \\ \hline
Transformationen, nicht lex. (CVA) & 600.000 & 378 & 97,0\% \\ \hline
Transformationen, lex.       & 950.000 & 690 & 96,6\% \\ \hline
Transformationen, nicht lex. & 950.000 & 621 & 96,2\% \\ \hline
\end{tabular}
\caption{Trefferrate unter verschiedenen Voraussetzungen}
\label{maintable}
\end{center}
\end{table}

Die Daten lassen folgende Schl"usse zu:
\begin{itemize}
\item Transformation-based error-driven learning kann mit stochastischen
Algorithmen auf Grundlage von $n$-grammen konkurrieren. Die erzielte
Genauigkeit "ubertrifft die des stochastischen Algorithmus deutlich; schon
mit einer kleinen Trainingsmenge von nur 64.000 W"ortern wird die Trefferrate
erreicht, f"ur die der stochastische Ansatz eine Trainingsmenge von 1.000.000
W"ortern ben"otigt.
\item Auch ohne vollst"andiges Lexikon ergibt sich noch eine sehr gute
Performance. Leider gibt es hierzu keine direkt vergleichbaren Daten anderer
Systeme. Erg"anzend ist anzumerken, da"s die Zahl der korrekt annotierten
\emph{unbekannten} W"orter bei der lexikalisierten Version des Algorithmus bei
82,2\% liegt. Andere (stochastische) Systeme zum Tagging unbekannter W"orter
\cite{weischedel} erreichen hier Werte bis 85\%, wobei das Modell allerdings
sehr speicherintensiv ist und bis zu $10^8$ Wahrscheinlichkeiten erfassen
mu"s, w"ahrend der vorgestellte Ansatz mit wenigen Regeln auskommt.
\item Die Lexikalisierung bringt nicht so viel zus"atzlichen Nutzen, wie man
das vielleicht erwarten k"onnte. Dies k"onnte evtl. daran liegen, da"s die
Datengrundlage nicht gro"s genug ist, um ausreichend viele wesentliche
wortabh"angige Transformationen lernen zu k"onnen (\emph{sparse data}).
\end{itemize}

Einen interessanten Zusammenhang sieht man in Abbildung \ref{diagramm}, das
f"ur die lexikalisierte Version des Algorithmus unter Annahme eines
vollst"andigen Lexikons bei einer Trainingsmenge von 600.000 W"ortern zeigt,
wie gro"s der Einflu"s der einzelnen Transformationen auf das Endergebnis ist.
Man kann erkennen, da"s die ersten Transformationen die Trefferrate rasch
ansteigen lassen, w"ahrend der Graph mit steigender Transformationszahl immer
weiter abflacht.

\begin{figure}[hbtp]
\begin{center}
\unitlength0.75mm
\begin{picture}(155.00,110.00)
\put(0,0){\framebox(155.00, 110.00){}}
\put(20.00,20.00){\vector(1,0){125.00}}
\put(57.00,10.00){\makebox(0,0)[l]{\# Transformationen}}
\put(28.01,20.00){\line(0,-1){1.00}}
\put(28.01,17.00){\makebox(0,0)[t]{0}}
\put(53.00,20.00){\line(0,-1){1.00}}
\put(53.00,17.00){\makebox(0,0)[t]{100}}
\put(77.98,20.00){\line(0,-1){1.00}}
\put(77.98,17.00){\makebox(0,0)[t]{200}}
\put(102.96,20.00){\line(0,-1){1.00}}
\put(102.96,17.00){\makebox(0,0)[t]{300}}
\put(127.94,20.00){\line(0,-1){1.00}}
\put(127.94,17.00){\makebox(0,0)[t]{400}}
\put(20.00,20.00){\vector(0,1){80.00}}
\put(20.00,102.00){\makebox(0,0)[b]{Trefferrate}}
\put(20.00,34.94){\line(-1,0){1.00}}
\put(17.00,34.94){\makebox(0,0)[r]{93\%}}
\put(20.00,51.65){\line(-1,0){1.00}}
\put(17.00,51.65){\makebox(0,0)[r]{94\%}}
\put(20.00,68.35){\line(-1,0){1.00}}
\put(17.00,68.35){\makebox(0,0)[r]{95\%}}
\put(20.00,85.06){\line(-1,0){1.00}}
\put(17.00,85.06){\makebox(0,0)[r]{96\%}}
\drawline(27.58,25.00)(28.23,50.74)(29.74,61.13)(30.60,64.74)(31.89,70.16)(33.18,73.32)(36.63,78.29)(40.94,81.68)(47.83,84.61)(54.29,87.32)(65.49,89.50)(102.96,93.60)(140.00,95.00)
\end{picture}
\end{center}
\vspace{-0.4cm}
\caption{Trefferrate in Abh"angigkeit von der Transformationszahl}
\label{diagramm}
\end{figure}

\section{Bewertung}
Mit diesen Daten in der Hand kann man nun versuchen, den vorliegenden Ansatz
zu bewerten und gegen"uber stochastischen Taggern abzugrenzen. Was sind also
die Vor- und Nachteile der vorgestellten Technik?

\begin{itemize}
\item Hinsichtlich der Effektivit"at nehmen sich die beiden Ans"atze nicht
viel. Leichten Vorteilen der transformations-basierten Methode insgesamt steht
ein Vorteil des stochastischen Ansatzes bei unbekannten W"ortern gegen"uber.
\item Die transformations-basierte Methode liefert als Ausgabe eine kleine
Anzahl von Regeln. Dies ist verglichen mit den umfangreichen
Wahrscheinlichkeitstabellen eines $n$-gramm-Taggers eine sehr kompakte
Darstellung, und noch dazu eine, die Menschen gut zug"anglich ist. So k"onnte
man etwa einen vollwertigen Tagger als Startannotierer der vorgestellten
Methode verwenden und anhand der gelernten Regeln eventuelle M"angel dieses
Taggers identifizieren (und hoffentlich beheben).
\item Laufzeitbetrachtungen sehen den transformationsbasierten Algorithmus
klar im Vorteil. Die erzeugten Transformationslisten lassen sich in einen
deterministischen endlichen Automaten umwandeln, der nach Angaben der Autoren
einen Tagging-Algorithmus erm"oglicht, der zehnmal so performant ist wie die
schnellsten stochastischen Tagger. Allerdings geht bei der Umwandlung in einen
Automaten naturgem"a"s die angesprochene kompakte Repr"asentation verloren.
\item Interessant w"aren auch Informationen "uber die Laufzeit des
\emph{Lernalgorithmus}. Zwar ist dies weniger kritisch, da nur einmal gelernt
werden mu"s, aber die Autoren bleiben die Information schuldig, ob das
Lernverfahren auch bei umfangreicheren Trainingstexten praktikabel bleibt.
\item Beide Algorithmen sind weitgehend sprachunabh"angig, werden aber bei
Sprachen mit einer komplett anderen Morphologie als Englisch Schwierigkeiten
haben. Sie betrachten ausschlie"slich \emph{lokale} Informationen, was bei
manchen sprachlichen Konstrukten etwa der deutschen Sprache problematisch ist
(z.B.~erweiterter Infinitiv mit \emph{zu} oder Trennung von Modalverb und
Partizip). Dies kann man jedoch nicht den Algorithmen anlasten. Festzuhalten
ist auch, da"s der pr"asentierte Lernalgorithmus f"ur unbekannte W"orter im
Gegensatz zu dem zum Vergleich herangezogenen Algorithmus \cite{weischedel}
sprachunabh"angig ist.
\end{itemize}

\bibliographystyle{gerplain}
%%% Der BibTeX-Stil "gerplain" ist die deutsche Variante des Standardstils
%%% "plain". Falls er nicht zur Verfuegung steht, diese Zeile durch "plain"
%%% ersetzen; dann stehen allerdings an einigen Stellen englische Woerter
%%% (z. B. "and" statt "und" sowie "editor"/"editors" statt "Herausgeber").

\bibliography{tbedl}

\end{document}
